The present invention is in the field of data processing and, in particular, relates to high speed auxiliary memories.
In many data processing systems where service is provided to a number of users, it is preferred to make use of a virtual memory architecture. Typically, virtual memory is divided into segments each of which is further divided into pages with each page accomodating a predetermined maximum number of words. In a number of systems, for example the Series 50 systems manufactured by Prime Computer, Inc. of Framingham, Mass., the addresses of the segments and pages are allocated by an operating system and can be arranged in the main memory in a random fashion. To the user, however, an appearance of continuity and unlimited memory space is presented and the user need not be concerned with the actual interleaved nature of programs in the main memory.
Because of the distributed reality of programs within the main memory as well as the time and energy necessary to retrieve data from the memory, it is also preferred to employ a smaller auxiliary memory or data cache to store data which are most likely to be needed by the user at a particular time. For this purpose, a data cache formed from Random Access Memory (RAM) units is often employed and typically stores 2 to 64 kilobytes of data. One convenient method for loading a data cache is to store data according to the lower order virtual address bits. For example, an entry at location 5 of a user's virtual page will be stored at location 5 in the data cache. However, this scheme alone does not assure that data retrieved from a particular location in the cache will be valid because a user can have more than one page of virtual memory and a data cache loaded in this fashion does not distinguish between virtual pages.
In order to validate data from the cache, an address translation is performed using an address tag (which is obtained along with the data from the cache when it is accessed) and an address translation element which is also most often implemented in RAM hardware. One known structure is called a lookaside buffer and essentially operates by storing main memory addresses and confirmation tags in association with particular virtual addresses. When the lookaside buffer is addressed, it returns a physical address and a tag to confirm the virtual address. If the physical address in the lookaside buffer does not match the address tag associated with the data, a data cache miss occurs (i.e., the data in the cache is from a different page) and the physical address from the lookaside buffer is and used to retrieve the proper data from the main memory.
It is also possible for a miss to occur in the lookaside buffer since only a finite number of address translations can be stored at any given time. Because virtual address space is so large, it is not practical to incorporate into the auxiliary memory a table that will tell a user where every page is located.
A number of techniques have been proposed for improving the process of address translation within the lookaside buffer. One technique, known as "hashing" is based upon the observation that users often do not program the full number of pages available in each of their segments. Instead, programs tend to execute in the beginning or first half of a segment. Therefore, an encoder can be used to "hash" some of the address bits which define the location of a page within a segment together with other address bits that define the segment number as well. The result is a "hash table" which fills the lookaside buffer according to a code with information from the virtual addresses (i.e., some of the lower bits that define the page as well as some of the bits that define the segment number) in a manner that ensures that the lookaside buffer contains more translations. Through hashing, the probability of finding an address translation in a lookaside buffer can be increased.
Nonetheless, a miss in the lookaside buffer can occur and causes substantial decline in computer performance. In most designs, microcoded instructions take over when an address miss occurs, freezing all data processing operations in mid-sequence and then prompting the operating system to find the virtual address translation. This problem can be serious in programs that have poor locality of reference.
One of the locality problems associated with address misses is called a "thrash" and occurs when two often-used components of a program compete for the same location in the lookaside buffer. A thrash can occur, when no hash table is used, if two related components of the program have identical address bit sequences and these sequences are chosen by the architecture to load the lookaside buffer. Similarly, a thrash can be created even when a hash table is employed to load the buffer if the addresses for two components of program are mapped into the same location in the buffer. Thrashing is most serious, for example, if a repetitive instruction and its operand must compete for the same location in the buffer; instead of performing a tight processing loop, the program is executed fitfully as the processor must employ microcoded instructions over and over again to obtain address translations .
There exists a need for improved address translation systems when used in conjunction with data caches to form high speed auxiliary memories. In particular, a system that could improve the efficiency of lookaside buffers in translating virtual-to-physical addresses would satisfy a long-felt need in the industry.